\documentclass[10pt,a4paper]{article}
\usepackage[utf8]{inputenc}
\usepackage{amsmath}
\usepackage{amsfonts}
\usepackage{amssymb}
\usepackage{hyperref}

\newcommand{\dist}[2]{d_{#1#2}}
\newcommand{\distij}{\dist{i}{j}}
\newcommand{\distji}{\dist{j}{i}}
\newcommand{\distik}{\dist{i}{k}}
\newcommand{\pij}{p_{ij}}
\newcommand{\eqg}{G_{\sigma}^{=}}
\newcommand{\aqg}{A_{\sigma}^{=}}
\newcommand{\eqt}{\eqts{\sigma}}
\newcommand{\eqtw}{\widetilde{\eqtree}^{\sigma}}
\newcommand{\eqtback}[1]{\overset{\twoheadleftarrow}{\rule{0pt}{1.2ex}\smash{\eqt}}(#1)}
\newcommand{\eqtforw}[1]{\overset{\twoheadrightarrow}{\rule{0pt}{1.2ex}\smash{\eqt}}(#1)}
\newcommand{\eqts}[1]{\eqtree^{#1}}
\newcommand{\eqtree}{\mathcal{T}}
\newcommand{\act}{\mathcal{O}}
\newcommand{\sg}{\widetilde{G}}
\newcommand{\sact}{\widetilde{\act}}
\newcommand{\sa}{\widetilde{A}}
\newcommand{\s}{\mathcal{S}^\sigma}
\newcommand{\f}{\mathcal{F}^\sigma}
%\newtheorem{theorem}{Theorem}
%\newtheorem{definition}{Definition}
%\newtheorem{lemma}{Lemma}
\newtheorem{notation}{Notation}
%\newproof{proof}{Proof}
\newtheorem{assumption}{Assumption}
\DeclareMathOperator*{\argmin}{arg\,min}


\newcommand{\alpharight}[1]{\alpha^{+}_{#1}}
\newcommand{\alphaleft}[1]{\alpha^{-}_{#1}}

\begin{document}
\section{Značení}
Značení z velké části přebíráme z článku:\\
$\eqt=(O,A)$ je strom s orientovanými hranami.\\
$\forall i\in O$ je definován start $i$ jako $\sigma(i)$ (pro jednoduchost budeme používat i $\sigma{O}$ pro start skupiny aktivit a $\sigma{G}$ pro start grafu (definice viz článek)\\
$\forall i\in O$ je definována konvexní cost function $c_i(t)$\\
Pro $\widetilde{G}\subseteq G$ definujeme shift cost function $sc_{\widetilde{G}}(t) = \sum_{i\in \widetilde{G}} c_i(t+\sigma(i))$\\
Pro účely dalšího textu zavedeme zjednodušené značení pro první derivaci shift cost function zprava: $sc_{\widetilde{G}}(\sigma(\widetilde{O}))'_{+} = \alpharight{G}$. Analogicky definujeme první derivaci zleva $\alphaleft{G}$.\\


\noindent Z předchozího plyne, že pojmy (strictly) \emph{early} a \emph{late} můžeme zavést následovně:\\
$\widetilde{G}\subseteq G$ je early právě tehdy, když $\alphaleft{\widetilde{G}}\leq 0$\\
$\widetilde{G}\subseteq G$ je late právě tehdy, když $\alpharight{\widetilde{G}}\geq 0$\\
$\widetilde{G}\subseteq G$ je strictly early právě tehdy, když $\alpharight{\widetilde{G}}<0$\\
$\widetilde{G}\subseteq G$ je strictly late právě tehdy, když $\alphaleft{\widetilde{G}}>0$\\
Všimněme si, že pojem early je definován pomocí levé derivace, zatímco když jde o strictly early, je v definici použita derivace pravá. Vycházíme totiž z úvahy, že co je early se nám nevyplatí posunout doleva (zajímáme se proto o tvar cost function vlevo od aktuální pozice), zatímco u strictly early se zajímáme o to, zda se vyplatí posunout doprava (zajímáme se proto o tvar cost function vpravo od aktuální pozice). Analogicky vše samozřejmě platí pro pojem late a strictly late. Dále si všimněme, že pokud je $\widetilde{G}$ strictly early, pak díky tomu že cost function je konvexní, je $\widetilde{G}$ i early.

\noindent Z toho vyplývá, že pojem aktivní hrana lze pak definovat jako:\\
$(i,j)\in A$ je aktivní právě tehdy, když platí jedna z následujících možností:
\begin{itemize}
\item $\alphaleft{\eqtback{(i,j)}}\leq 0$ a zároveň $\alphaleft{\eqtforw{(i,j)}}>0$\\(tj. $\eqtback{(i,j)}$ je early a $\eqtforw{(i,j)}$ je strictly late)
\item $\alpharight{\eqtback{(i,j)}}< 0$ a zároveň $\alpharight{\eqtforw{(i,j)}}\geq 0$\\(tj. $\eqtback{(i,j)}$ je strictly early a $\eqtforw{(i,j)}$ je late)
\item $\alpharight{\eqtback{(i,j)}}< 0$ a zároveň $\alphaleft{\eqtforw{(i,j)}}>0$\\(tj. $\eqtback{(i,j)}$ je strictly early a $\eqtforw{(i,j)}$ je strictly late)
\end{itemize}

\section{Cíl}
Nechť nám nepřítel dá strom s orientovanými hranami $\eqt=(O_{\eqt},A_{\eqt})$ takový, že:
\begin{itemize}
\item $\alphaleft{\eqt}\leq 0$ a zároveň $\alpharight{\eqt}\geq 0$ (tj. $\eqt$ je on time)
\item a zároveň pro podmnožinu aktivit $\widetilde{O}\subseteq O_{\eqt}$ platí $\alphaleft{\overleftarrow{\eqt}(\widetilde{O})} \leq 0$ a $\alpharight{\overrightarrow{\eqt}(\widetilde{O})} \geq 0$ (tj. že libovolný levý uzávěr je early a libovolný pravý uzávěr je late - tudíž $\eqt$ je optimální - jen to zrovna nemusí být active equality tree).
\end{itemize}

Hledáme takový řez stromu $\eqt$, že se $\eqt$ rozpadne na AEF $\f$ (samozřejmě takový, že všechny aktivity v $\eqt$ se nacházejí i v $\f$). Připomeňme že AEF je množina disjunktních active equality tree.

\emph{Poznámka1: Tento text se snaží vyřešit problém co s odpadlíky při posouvání stromu. Ti totiž vůbec nemusí být AET. Víme ovšem že splňují uvedené dvě podmínky. Jestli to bude stačit, uvidíme. Snad budeme mít štěstí}

\emph{Poznámka2: Původní zadání problému může obsahovat mnohem více hran, ale během posouvání stromů pracujeme jen s některými (těmi které tvořeí equality trees). Mlčky tu předpokládáme, že ty ostatní hrany nebudeme potřebovat. Je to vůbec pravda?}

\emph{Poznámka3: V článku jsme dokázali, že pokud máme AEF, pak je rozvrh optimální. Nikde jsme ale nedokázali, že pokud máme optimální rozvrh, pak existuje AEF. Doufám, že důkaz tohoto tvrzení bude úzce souviset s algoritmem pro vybudování AEF (viz níže) a že tak zabijeme dvě mouchy jednou ranou.}

\section{Algoritmus}
Uvažujme tedy ten nepřítelem daný strom $\eqt=(O_{\eqt},A_{\eqt})$ s výše uvedenými vlastnostmi. Jak z $\eqt$ udělat AEF? Nabízí se posup, že buď, že vezmeme $\eqt$ a z jeho množiny hran $A_{\eqt}$ budeme postupně nějaké hrany odstraňovat až dostaneme AEF. Nebo naopak nejprve vytvoříme les, kde každý strom bude tvořen jen jednou aktivitou a postupně budeme stromy spojovat hranami z $A_{\eqt}$ až získáme AEF.

Nevím proč, ale více se mi líbí durhá varianta (postupně utváříme AEF joinováním stromů). Zkusme z toho vyjít. Les na počátku vůbec nemusí být AEF, protože jednotlivé aktivity nemusí být on-time. Budeme vkládat hrany tak, aby stále platil následující invariant: Hrany ve všech stromech v lese jsou aktivní. (pokud tento invariant nebude splněn, algoritmus by hrany vkládal, pak jiné odebíral a zavání to hrubým prohledáváním všech možností. Rádi bychom zůstali jen u vkládání hran.

Na první pohled stačí spojovat stromy aktivními hranami, ale jak víme může se stát, že vložením jedné aktivní hrany do stromu může jiná hrana ve stromu přestat být aktivní. Například mám strom $i \rightarrow j$, kde $i$ je early a $j$ je strictly late. Celý strom je strictly late. Spojím se stromem o jednom vrcholu $k$ a to tak že, $k \rightarrow j$. Vrchol k mohl způsobit, že podstrom $k \rightarrow j$ přestal být strictly late, tudíž hrana $i \rightarrow j$ již není aktivní.

Z toho plyne, že vkládání hran musí probíhat nějak monotónně, aby se nenarušily již vytvořené struktury. Něco ve smyslu, že stromy, které mezi sebou vytvářejí největší tlak vezmu přednostně\ldots Mám strach že to trošku smrdí NP-C.

\newpage
Vyextrahoval (a asi i ořezal) jsem náš problém až na samou kost. 

Nejprve stručně slovně - mám orientovaný strom a každý vrchol je ohodnocen nějakými dvěma čísly $\alphaleft{}$ a $\alpharight{}$. Cílem je vyhodit z tohoto stromu nějaké (třeba i žádné) hrany tak, aby pro každou zbylou hranu platilo, že součet $\alphaleft{}$ všech vrcholů které visí vlevo od byl menší nebo rovno nula a součet $\alpharight{}$ vrcholů vpravo od ní byl větší nebo rovno nula.

Nyní to samé, ale formálně: 

Značení je analogicky převzaté z článku, ale pro úplnost zopakuji: Nechť $e=(i,j)$, pak $\overset{\twoheadleftarrow}{T}(e)$ označuje komponentu obsahující vrchol $i$, která by vznikla odstraněním hrany $e$ z grafu. Analogicky je definován $\overset{\twoheadrightarrow}{T}(e)$. Význam čísel $\alphaleft{}$ a $\alpharight{}$ v tomto zadání není podstatný - jsou to prostě nějaká reálná čísla. Jejich návaznost na náš problém je popsána v textu výše.

Samotné formální zadání pak zní: Nechť (V,E) je orientovaný strom. Nechť je každý vrchol $v\in V$ ohodnocen dvěma hodnotami $\alphaleft{v}\in R$ a $\alpharight{v}\in R$. Hledáme takovou podmnožinu vrcholů $\widetilde{E}\subseteq E$, že pro všechny hrany $e\in \widetilde{E}$ bude ve stromu $T=(V,\widetilde{E})$ platit, že $\sum_{v\in \overset{\twoheadleftarrow}{T}(e)}{\alphaleft{v}}\leq 0$ a $\sum_{v\in \overset{\twoheadrightarrow}{T}(e)}{\alpharight{v}}\geq 0$ (*).  

Snažil jsem se na řešení přijít ale marně. Snažil jsem se uvažovat postup, kdy je množina $\widetilde{E}$ zprvu prázdná a já do ní hrany nějak chytře vkládám. Invariantem během vkládání by muselo být, že pro každou hranu platí ty nerovnosti v zadání viz (*) a nově přidaná hrana mi tyto nerovnosti nerozbije, což jak se ukazuje není snadné (je-li to vůbec možné). Nově přidaná hrana totiž může ovlivnit jinou hranu na druhém konci stromu. Pokud budu uvažovat její sílu příspěvku (tj. velikost $\alphaleft{}$ či $\alpharight{}$) tak si také nepomohu, protože se mi může vyskytnout například milion hran s malým příspěvkem, které ovšem vedou do stejného vrcholu - ve výsledku mohou tak mít i hrany s malým příspěvkem na jednom konci stromu velký dopad na hrany na druhém konci stromu.

Dál už jen trochu brainstormingu:

nesnažíme se řešit nějaký NP-c problém? V podstatě zda hrana v množině bude nebo ne trošku zavání kombinatorikou. Nevede mi tahle úloha na například na  \href{http://en.wikipedia.org/wiki/Integer_programming}{integer programming}

Nebo není to třeba nějaký druh \href{http://en.wikipedia.org/wiki/Minimum_k-cut}{minimum k-cut} problému nebo \href{http://en.wikipedia.org/wiki/Capacitated_minimum_spanning_tree}{capacitated minimum spanning tree}? Dejme tomu, že nám protivník dává úlohy takového typu, že $\forall v \in V$ je vždy $\alpharight{v} > 0$. Pak podmínka $\sum_{v\in \overset{\twoheadrightarrow}{T}(e)}{\alpharight{v}}\geq 0$ bude splněna vždy, tudíž ji můžeme z definice problému vyhodit. V tomto případě ztrácí smysl předpokládat orientovanost grafu a úloha se nám zredukovala na: Nechť je dán graf $G=(V,E)$, nechť je každý vrchol $v\in V$ ohodnocený $\alpha_{v}\in R$. Hledáme graf, ve kterém je $\sum_{v\in \overset{\twoheadleftarrow}{T}(e)}{\alpha_{v}}\leq 0$\ldots to na minimum k-cut nevede.

Nebo co když se zadání omezí na $\alphaleft{}=\alpharight{}$ - vrchol pak bude mít nějaké jedno ohodnocení. Zbytek zadání zůstává stejný. To také není žádná známá NP-c úloha.
\end{document}